#include <cstdio>
#include <cstring>

int e, head[ 100010 ], node[ 100010 ], next[ 100010 ], a[ 100010 ], n, m;
int f[ 1001 ][ 1001 ], f2[ 1001 ][ 1001 ];

void addedge( int u, int v )
{
    node[ e ] = v; next[ e ] = head[ u ]; head[ u ] = e++;
}

void init( )
{
    int i, j, u, v;
    memset( head, -1, sizeof( head ) );
    e = 0;
    for ( i = 1; i <= n; i++ )
    {
        scanf("%d%d", &u, &v);
        a[ i ] = v;
        addedge( u, i );
    }
    memset( f, -1, sizeof( f ) );
    for ( i = 0; i <= 1000; i++ ) f[ i ][ 0 ] = 0;
}

void dp( int p, int deep )
{
    int i, v, j, k;
    for ( i = 0; i <= m; i++ ) f2[ deep ][ i ] = f[ deep ][ i ];
    for ( i = m; i >= 1; i-- )
        if ( f2[ deep ][ i ] < f2[ deep ][ i - 1 ] + a[ p ] && f2[ deep ][ i - 1 ] != -1 )
            f2[ deep ][ i ] = f2[ deep ][ i - 1 ] + a[ p ];
    for ( i = head[ p ]; i != -1; i = next[ i ] )
    {
        v = node[ i ];
        for ( j = 0; j <= m; j++ )
            f[ deep + 1 ][ j ] = f[ deep ][ j ];
        dp( v, deep + 1 );
        for ( j = 0; j <= m; j++ )
            if ( f[ deep ][ j ] < f[ deep + 1 ][ j ] )
                f[ deep ][ j ] = f[ deep + 1 ][ j ];
    }
    for ( i = 0; i <= m; i++ )
        if ( f[ deep ][ i ] < f2[ deep ][ i ] )
            f[ deep ][ i ] = f2[ deep ][ i ];
}

int main( )
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        if ( n == 0 && m == 0 ) break;
        init( );
        dp( 0, 0 );
        if ( f[ 0 ][ m ] == -1 )
            puts("0");
        else
            printf("%d\n", f[ 0 ][ m ]);
    }
    return 0;
}
